﻿using System;
using Algoritmia.DataStructures.Lists;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Knapsack
{
    public class MemoizedKnapsackSolver : IKnapsackSolver
    {
        private readonly Func<int, int, IMap<Tuple<int, int>, double>> _createMap;

        public MemoizedKnapsackSolver(Func<int, int, IMap<Tuple<int, int>, double>> createMap = null)
        {
            _createMap = createMap ?? ((a,b) => AlgoritmiaFactory.Maps<Tuple<int, int>, double>.Default);
        }

        public double Profit(int W, IList<double> values, IList<int> weights)
        {
            var N = values.Count;
            var mem = _createMap(N,W);

            Func<int, int, double> B = null;
            B = (n, c) =>
                    {
                        if ( n == 0)
                        {
                            return 0;
                        }
                        var tp1 = new Tuple<int, int>(n - 1, c);
                        if (!mem.Contains(tp1))
                        {
                            mem[tp1] = B(n - 1, c);
                        }

                        if ( c - weights[n-1] >= 0)
                        {
                           
                            var tp2 = new Tuple<int, int>(n - 1, c - weights[n - 1]);
                            if ( !mem.Contains(tp2))
                            {
                                mem[tp2] = B(n - 1, tp2.Item2);
                            }
                            return Math.Max(mem[tp1], mem[tp2] + values[n-1]);
                        }
                        else
                        {
                            return mem[tp1];
                        }
                    };

            var finalCall = new Tuple<int, int>(N, W);
            mem[finalCall] = B(N, W);
            return mem[finalCall];
        }
    }
}
